/*******************************************************************************
 * Copyright 2010 DemandSpot
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 ******************************************************************************/
package com.demandspot.utils.searchtree;

import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import org.apache.commons.lang.StringUtils;
import org.apache.log4j.Logger;

public class SearchTreeBuilder<T extends SearchTreeElement> {

	private static final Logger logger = Logger.getLogger(SearchTreeBuilder.class);
	
	SearchTreeBuilder() {
    }
    
    /**
     * Builds a prefix search tree for a given List of SearchTreeElement
     * 
     * @param elements List of SearchTreeElements
     * @param maxTreeLevels max levels (prefix) for fast searching after this level the search for a given prefix will be performed with
     * 						String.startsWith method 
     * @return SearchTree
     */
    SearchTree<T> buildSearchTree(SearchTree<T> searchTree, List<T> elements, Comparator<T> sameElementsComparator, int maxTreeLevels) {
        Iterator<T> listIter = elements.iterator();
        
        //Loop over the elements
        while (listIter.hasNext()) {
            T element = listIter.next();
            addNode(sameElementsComparator, searchTree, element, maxTreeLevels);
		}
        return searchTree;
    }

	void addNode(Comparator<T> sameElementsComparator, SearchTree<T> searchTree, T element, int maxTreeLevels) {
		String[] fullKeys = element.getKeys();
		
		for(String fullKey : fullKeys) {
			SearchTree<T> currentTree = searchTree;
		    //remove any unwanted white spaces
		    String[] fullKeyArr = fullKey.split("\\s");
		    fullKey = StringUtils.join(fullKeyArr, " ").toLowerCase();
		    
			String key = fullKey;
			//build the search nodes for the element key
			for (int i = 0; ((maxTreeLevels == -1 || i < maxTreeLevels) && i < key.length()); i++) {
				String nodeKey = key.substring(i, i + 1);
				SearchTreeNode<T> node = currentTree.getTreeNode(nodeKey);

				if (node == null) {					
					node = new SearchTreeNode<T>(sameElementsComparator);
					node.setLevel(i + 1);
					node.setParent(currentTree);
					node.setKey(nodeKey);
					currentTree.addTreeNode(node);
				}

				node.addElement(element);

				if (node.getTree() == null) {
					SearchTree<T> nodeTree = new SearchTree<T>();
					nodeTree.setParent(currentTree);
					node.setTree(nodeTree);
				}

				currentTree = node.getTree();
			}
		}
	}
}
